package tree;

public class TreeNode {
    private int value;
    private TreeNode leftNode;
    private TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    public void insert(int newValue) {
        if (newValue < value) {
            if (leftNode == null) {
                leftNode = new TreeNode(newValue);
                return;
            }
            leftNode.insert(newValue);
        } else if (newValue > value) {
            if (rightNode == null) {
                rightNode = new TreeNode(newValue);
                return;
            }
            rightNode.insert(newValue);
        }
        return;
    }

    public int getLeftValue() {
        return this.leftNode != null ? this.leftNode.getValue() : Integer.MIN_VALUE;
    }

    public int getRightValue() {
        return this.rightNode != null ? this.rightNode.getValue() : Integer.MAX_VALUE;
    }

    public String getMiddleTravle() {
        String result = "";
        if (this.leftNode != null) {
            result += this.leftNode.getMiddleTravle();
        }

        result += String.valueOf(value);

        if (this.rightNode != null) {
            result += this.rightNode.getMiddleTravle();
        }

        return result;
    }

    public TreeNode find(int value) {
        if (this.value == value) {
            return this;
        }

        if (value < this.value && this.leftNode != null) {
            return this.leftNode.find(value);
        }
        else if (value > this.value && this.rightNode != null) {
            return this.rightNode.find(value);
        }
        return null;
    }

    // 逻辑有缺陷
    public TreeNode remove(int value) {
        if (value < this.value && this.leftNode != null) {
            this.leftNode = this.leftNode.remove(value);
        }
        else if (value > this.value && this.rightNode != null) {
            this.rightNode = this.rightNode.remove(value);
        }

        if (value == this.value) {
            if (this.leftNode == null && this.rightNode == null) {
                return removeWithNoChild();
            }
            else if (this.leftNode != null && this.rightNode != null) {
                return removeWithTwoChildren();
            }
            return removeWithOneChild();
        }
        return this;
    }

    private TreeNode removeWithNoChild() {
        return null;
    }

    private TreeNode removeWithOneChild() {
        return this.rightNode == null ? this.leftNode : this.rightNode;
    }

    private TreeNode removeWithTwoChildren() {
        TreeNode min = this.rightNode;
        TreeNode minP = this;

        while (min.leftNode != null) {
            minP = min;
            min = min.leftNode;
        }

        this.value = min.value;
        minP.leftNode = null;
        return this;
    }
}
